/* 494. 目标和 */
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

/* 回溯 */
var findTargetSumWays = function (nums, target) {
	let count = 0
	const backtrack = (nums, target, index, sum) => {
		if (index === nums.length) {
			if (sum === target) count++
		} else {
			backtrack(nums, target, index + 1, sum + nums[index])
			backtrack(nums, target, index + 1, sum - nums[index])
		}
	}
	backtrack(nums, target, 0, 0)
	return count
}

/* 
    dp 
    dp[i][j] 表示在数组nums的前i个数中选取元素使得这些元素之和为j的方案
    假设数组nums的长度为n，则最终答案为dp[n][neg]


    当没有任何可以选取时，元素和只能是0 对应的方案数是1 因此动态规划的边界条件是:
    dp[0][j] = {
        1:j = 1
        0:j>=1 
    }
    当 1<= i <= n 对于数组 nums 中的第i个元素num(i的计数从1开始)
    遍历0 <= j <= neg 计算dp[i][j] 的值
    如果 j < num 则不能选num 此时 d[i][j] = dp[i-1][j]
    如果j >= num 则如果不能选num 方案数是dp[i-1][j] 如果选num 方案数
    是dp[i-1][j - num]
    此时有 dp[i][j]={
        dp[i-1][j] (j < num[i])
        dp[i-1][j] + dp[i-1][j-nums[i]] (j >= nums[i])
    }
*/

var findTargetSumWays = function (nums, target) {
	let sum = 0
	for (const num of nums) {
		sum += num
	}
	const diff = sum - target
	/* 一正一负要抵消 所以差值为偶数 */
	if (diff < 0 || diff % 2 !== 0) return 0
	const n = nums.length,
		neg = diff / 2

	const dp = new Array(n + 1).fill(0).map(() => new Array(neg + 1).fill(0))
	dp[0][0] = 1
	for (let i = 1; i <= n; i++) {
		const num = nums[i - 1]
		for (let j = 0; j <= neg; j++) {
			dp[i][j] = dp[i - 1][j]
			if (j >= num) {
				dp[i][j] += dp[i - 1][j - num]
			}
		}
	}

	return dp[n][neg]
}

/* 滚动数组优化 */
var findTargetSumWays = function (nums, target) {
	let sum = 0
	for (const num of nums) {
		sum += num
	}
	const diff = sum - target
	/* 一正一负要抵消 所以差值为偶数 */
	if (diff < 0 || diff % 2 !== 0) return 0
	const neg = Math.floor(diff / 2)
	const dp = new Array(neg + 1).fill(0)
	dp[0] = 1

	for (const num of nums) {
		for (let j = neg; j >= num; j--) {
			dp[j] += dp[j - num]
		}
	}

	return dp[neg]
}
